package org.example.myleet.p881;

import java.util.Arrays;

/**
 * 思路：排序+双指针
 * 排序后，较轻的人排在左边，较重的人排右边，需要证明贪心的思路正确性：每次组合必须组合一个数组里面最轻的人
 * 反证法：如果组合的不是数组里面最轻的人，那么一定存在最轻的人可以另外组合一个较重的人，或者这个最轻的人可以替换不是最轻的人
 * 官方的思路：若他不能与体重最重的人同乘一艘船，那么体重最重的人无法与任何人同乘一艘船，此时应单独分配一艘船给体重最重的人；若他能与体重最重的人同乘一艘船，那么他能与其余任何人同乘一艘船，为了尽可能地利用船的承载重量，选择与体重最重的人同乘一艘船是最优的。
 */
public class Solution {
    public int numRescueBoats(int[] people, int limit) {
        //先给数组排序
        Arrays.sort(people);
        int count = people.length;
        //对向移动双指针，l代表体重轻的人，r代表体重比较重的人
        int l = 0, r = people.length - 1;
        while (l < r) {
            if (people[l] + people[r] <= limit) {
                //如果双指针指向的人的组合不超过limit，说明可以组合在一起以减少一艘救生艇
                --count;
                //体重轻的人已组合，左指针向右移动
                ++l;
            }
            //不管是能组合还是不能组合，右指针都需要向左移动
            --r;
        }
        //返回最终需要的救生艇数量
        return count;
    }
}
